package code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class BestTime {
	
    public int climbStairs(int n) {
        int i;
        int[] fb=new int[n+1];
        fb[0]=fb[1]=1;
        for(i=2;i<=n;i++)
        	fb[i]=fb[i-1]+fb[i-2];
        return fb[n];
    }
    public void dfs(int n,int step,int[] rec,int[] num,boolean[] vis,List<List<Integer>> result){
    	if(n==step){
    		List<Integer> list=new ArrayList<Integer>();
    		for(int i=0;i<step;i++){
    			list.add(rec[i]);
    		}
    		result.add(list);
    		return ;
    	}
    	for(int i=0;i<n;i++){
    		if(vis[i] || (i>0 && num[i]==num[i-1] && !vis[i-1]))
    			continue;
    		if(!vis[i]){
    			vis[i]=true;
    			rec[step]=num[i];
    			dfs(n,step+1,rec,num,vis,result);
    			vis[i]=false;
    		}
    	}
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
    	List<List<Integer>> ans=new ArrayList<List<Integer>>();
    	int n=nums.length;
    	if(n==0) return ans;
    	Arrays.sort(nums);
    	int[] rec=new int[n];
    	dfs(n,0,rec,nums,new boolean[n],ans);
    	return ans;
    }
    public static void main(String[] args){
//    	BestTime bt=new BestTime();
//    	for(int i=2;i<10;i++)
//    		System.out.println(bt.climbStairs(i));
    	int[] nums={1,1,2};
    	new BestTime().permuteUnique(nums);
    }
}
